// 有序数组，查找n出现的第一次和最后一次位置

// 第一种  直接for

const findIndexAndLastIndex = (array, n) => {
  const indexArr = [-1, -1];

  // 做个类型处理
  if (!array || !Array.isArray(array)) return indexArr;

  // 长度单独
  const length = array.length;
  // 做个边界处理
  if (array[0] > n || array[length - 1] < n) return indexArr;

  for (let i = 0; i < length; i++) {
    // 第一次出现  判断标准就是indexArr[0] !== -1
    if (array[i] === n && indexArr[0] === -1) {
      indexArr[0] = i;
    }

    // 最后一次出现，判断标准是array[i+1]>n || i=== length-1
    if (array[i] === n && (array[i + 1] > n || i === length - 1)) {
      indexArr[1] = i;
    }

    // 中间有可能不存在 就退出循环
    if (array[i] > n) break;
  }

  return indexArr;
};

// 第二种，从中间开始

const find2 = (array, n) => {
  const indexArr = [-1, -1];

  // 做个类型处理
  if (!array || !Array.isArray(array)) return indexArr;

  // 长度单独
  const length = array.length;
  // 做个边界处理
  if (array[0] > n || array[length - 1] < n) return indexArr;

  // 找到会出现的位置
  let existIndex = -1;

  // 辅助函数
  const findHelp = (first, last) => {
    // 这个就是找不到了
    if (last === first) return;

    // 从中间查找
    const mid = Math.floor((first + last) / 2);
    if (array[mid] === n) {
      existIndex = mid;
      return;
    }

    if (array[mid] > n) findHelp(first, mid);
    if (array[mid] < n) findHelp(mid, last);
  };

  // 查找
  findHelp(0, array.length - 1);

  // 如果存在
  if (existIndex !== -1) {
    let first = (last = existIndex);

    while (array[first] === n && first >= 0) {
      first--;
    }

    while (array[last] === n && last < length) {
      last++;
    }
    indexArr[0] = first + 1;
    indexArr[1] = last - 1;
  }

  return indexArr;
};

const index = findIndexAndLastIndex(
  [1, 2, 3, 4, 5, 5, 5, 6, 7, 7, 7, 8, 8, 8, 8, 9],
  5
);

const exist = find2([1, 2, 3, 4, 5, 5, 5, 6, 7, 7, 7, 8, 8, 8, 8, 9], 5);

console.log(index, exist);
